#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<queue>
#include <map>

using namespace std;

//class Solution {
//public:
//    void _compressString(string& ret, string& param, int& i)
//    {
//        int n = param.size();
//
//        char s = param[i];
//        int num = 1;
//        for (i = i + 1; i < n; ++i)
//        {
//            if (param[i] == s)
//                ++num;
//            else break;
//        }
//        ret += s;
//        if (num > 1)          
//        { 
//            string tmp = to_string(num);
//            ret += tmp;
//        }
//    }
//
//    string compressString(string& param)
//    {
//        string ret;
//        int n = param.size();
//        ret.reserve(n);
//
//        int i = 0;
//        while (i < n)
//        {
//            _compressString(ret, param, i);
//        }
//        return ret;
//
//    }
//};
//
//int main()
//{
//    string s = "qjjjJJJJjjqeeeeeeqkkkkJJJJkkkqeeeeee";
//    cout << Solution().compressString(s) << endl;
//    return 0;
//}

//typedef long long ll;
//struct Greater
//{
//    bool operator()(pair<ll, ll> p1, pair<ll, ll> p2)
//    {
//        return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);
//    }
//};
//
//int main() {
//    ll n, k;
//    while (cin >> n >> k)
//    {
//        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, Greater> pq;
//        vector<ll> _sour(n);
//        vector<ll> _sweet(n);
//
//        for (ll i = 0; i < n; ++i)
//        {
//            cin >> _sour[i];
//        }
//        for (ll i = 0; i < n; ++i)
//        {
//            cin >> _sweet[i];
//        }
//
//        for (ll i = 0; i < n; ++i)
//        {
//
//            pair<ll, ll> tmp = { _sour[i], _sweet[i] };
//            if (pq.size() < k)
//            {
//                pq.push(tmp);
//            }
//            else
//            {
//                if (Greater()(tmp, pq.top()))
//                {
//                    pq.pop();
//                    pq.push(tmp);
//                }
//            }
//        }
//
//        ll sour = 0;
//        ll sweet = 0;
//        while (pq.size())
//        {
//            sour += pq.top().first;
//            sweet += pq.top().second;
//            pq.pop();
//        }
//        cout << sour << " " << sweet << endl;
//    }
//    return 0;
//}



class Solution {
public:
    int knapsack(int V, int n, vector<vector<int>>& vw)
    {
        multimap<double, pair<int, int>, greater<double>> v;

        for (int i = 0; i < n; ++i)
        {
            v.insert({ (double)vw[i][1] / vw[i][0], {vw[i][0], vw[i][1]} });
        }

        int volume = 0;
        int weigth = 0;
        auto it = v.begin();
        while (volume <= V && it != v.end())
        {
            if (volume + (*it).second.first <= V)
            {
                weigth += (*it).second.second;
                volume += (*it).second.first;
                ++it;
            }
            else break;
        }

        return weigth;

    }
};

int main()
{
    vector<vector<int>> vv = { {1,3}, {9,8} };
    cout << Solution().knapsack(10, 2, vv) << endl;
    return 0;
}